

#ifndef __TREE_HPP__
#define __TREE_HPP__

#include "CxType.h"
#include <iostream>



BEGIN_CX  

template 	<	
			typename _Key,
			typename _Type
			> 
struct BinaryTree
{
	BinaryTree	(_Key key_,_Type value_):value(value_),key(key_),
					left(NULL),right(NULL),height(0){}
	virtual	~BinaryTree(){}
	_Key			key;
	_Type 			value;
	uint			height;
	BinaryTree 	*	left;
	BinaryTree 	*	right;
};

template <	typename _Key,typename _Type	>
class SortedTree
{
public:

	typedef _Key					_KeyType;
	typedef _Type					_ValueType;
	typedef uint 					_CxResult;
	
private:

	typedef BinaryTree<_KeyType,_ValueType> 	_NodeType;
	
public:

	SortedTree():_head(NULL),_size(0),_mheight(0){}
	virtual  	~SortedTree()
	{
		clear();
	}

public:
	
	SortedTree(const SortedTree &src)
	{
		_head		=		NULL;
		_copy_all_data(src._head,this->_head);
		_size		=	src._size;
		_mheight	=	src._mheight;
	}

public:


	SortedTree & operator = (const SortedTree &src)
	{
		clear();
		_copy_all_data(src._head,this->_head);
		_size		=	src._size;
		_mheight	=	src._mheight;

		return *this;
	}


public:

	uint			size()const{return _size;}
	
	uint			mheight()const{return _mheight;}
	
	/* Insert value*/
	_CxResult		insert(const _KeyType key,const _ValueType &value)
	{
		
		_NodeType *node=NULL;
		_CxResult 	result;
		if( _head == NULL)
		{
			_head=new _NodeType(key,value);
			_head->height=0;
			goto SUCCEED;
		}
			
		result = _insert(_head,key,value);
		if(result == CX_INST_OK )
			goto SUCCEED;
		
	FAILED:
			return result;
	SUCCEED:
			++_size;
			return CX_OK;
	}
	
	/*	Insert value*/
	_CxResult 		insert(const _KeyType key,const _ValueType && value)
	{
		_ValueType  tmp(value);
		return insert(key,tmp);	
	}
	
	/* Delete Value*/
	_CxResult		del_node(_KeyType key)
	{
		return 	_del_node(key);
	}
	
	/* Find value without parent */
	_NodeType * 	find_value(_KeyType key)
	{
		_NodeType *pt;
		if(_findvalue(_head,key,pt)!=CX_NO_VALUE)
			return pt;
		else 
			return NULL;
	}
	
	/* Find value with parent node */
	_NodeType * 	find_value(_KeyType key ,_NodeType *&parent)
	{
		_NodeType *pt;
		if(_findvalue(_head,key,pt,parent)!=CX_NO_VALUE)
			return pt;
		else 		
			return NULL;	
	}
	
	/* Clear all data*/
	void			clear()
	{
		_del_all_node(_head);
		_size=0;
		_mheight=0;
	}

protected:
	_CxResult 		_del_node(_KeyType key)
	{
		static uint count=0;
			
		_NodeType *parent,*node,*max;
		
		if( _head->key == key )
		{
			node=_head;		
			if(!node->left)
				_head=node->right;
			else if(!node->right)
				_head=node->left;
			else 
			{
				_head=node->left;
				max=_findmax(node->left);
				if(max)
					max->right=node->right;
			}
			
			/* Update child tree Height */
			if(_head)		
				_update_height ( _head , -1);
			
			
			delete node;
			return CX_POP_OK;
		}
		
		if( _findvalue(_head,key,node,parent) != CX_NO_VALUE )
		{
			/* storage parent pointer*/
			_NodeType *& pnode=( parent->left->key==node->key )?
												parent->left:parent->right;
												
			/* adjust pointer */
			if(!node->left)
				pnode=node->right;
			else if(!node->right)
				pnode=node->left;
			else 
			{
				pnode=node->left;
				max=_findmax(node->left);
				if(max)
					max->right=node->right;
			}
			
			/* update child tree height */		
			if(pnode)
				_update_height ( pnode , parent->height);
			
			delete node;
			return CX_POP_OK;
		}
		else 
			return CX_NO_VALUE;
		
	}
	
	void			_del_all_node(_NodeType		*&node)
	{
		if(node ==	NULL)
			return ;

		_NodeType	*left	=	node->left;
		_NodeType	*right	=	node->right;

		delete node;
		node=	NULL;

		if( left != NULL)
			_del_all_node(left);
		if(	right !=NULL)
			_del_all_node(right);
	}

	void			_copy_all_data(const _NodeType *src,_NodeType *&dest)
	{
		if(src ==	NULL)
			return ;
		
		dest			=	new _NodeType(src->key,src->value);
		dest->height	=	src->height;
		dest->left		=	NULL;
		dest->right		=	NULL;
		
		_copy_all_data(src->left,dest->left);
		_copy_all_data(src->right,dest->right);

	}
	
	_CxResult 		_findvalue(_NodeType *node,_KeyType key,_NodeType *&pt)
	{
		if(node==NULL)
		{
			pt=NULL;
			return CX_NO_VALUE;
		}
		
		if(key == node->key)
		{
			pt=node;
			return CX_OK;
		}
			
		if(key > node->key)
			return _findvalue (node->right,key,pt);
		else 
			return _findvalue (node->left,key,pt);
	}
	
	_CxResult 		_findvalue (_NodeType *node,_KeyType key,_NodeType *&pt,_NodeType *&parent)
	{
		if(node==NULL)
		{
			pt=NULL;
			parent=NULL;
			return CX_NO_VALUE;
		}
		
		if(key > node->key)
		{
			if( node->right && key == node->right->key)
			{
				parent=node;
				pt=node->right;
				return CX_OK;
			}
			else 
				return  _findvalue (node->right,key,pt,parent); 
		}
		
		else 
		{			
			if( node->left && key == node->left->key)
			{
				parent=node;
				pt=node->left;
				return CX_OK;
			}
			
			else 
				return 
					_findvalue (node->left,key,pt,parent); 	
		}
	}
	
	_NodeType		*_findmin(_NodeType * node)
	{
		if(node->left == NULL )
			return node;
		else 
			return _findmin(node->left);
	}
	
	_NodeType 		*_findmax(_NodeType *node)
	{
		if(node->right == NULL)
			return node;
		else 
			return _findmax(node->right);
	}
	
	_CxResult		_insert(_NodeType *node ,const _KeyType key,const _ValueType &value)
	{
		
		if(key == node->key)
			return CX_EXISTING;
					
		else if(key > node->key)
		{
			if(node->right==NULL)
			{
				node->right=new _NodeType(key,value);
				node->right->height=node->height+1;
				if(node->right->height > _mheight)
					_mheight = node->right->height;
				return CX_INST_OK;
			}
			else 
				return _insert(node->right,key,value);
		}
		else 
		{
			if(node->left==NULL)
			{
				node->left=new _NodeType(key,value);
				node->left->height=node->height+1;
				if(node->left->height > _mheight)
					_mheight = node->left->height;
				return CX_INST_OK;
			}
			else 
				return _insert(node->left,key,value);
		}
	}
			
	void			_update_height(_NodeType *node,int parent_height)
	{
		if(node == NULL)
			return ;
		else
		{
			node->height = parent_height + 1 ;
			_update_height ( node->left  , node->height );
			_update_height ( node->right , node->height );
		}
	}

private:

	_NodeType 		*_head;
	uint			_size;
	uint			_mheight;
};

END_CX

#endif
